package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: CountBits338
 * @description: 给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
 * @date 2021/3/310:54
 * @since V1.0
 */
public class CountBits338 {
    //动态规划 位运算 二进制
    //arr[i] = arr[2的幂] (1) + arr[i-2的幂]
    public int[] countBits(int num) {
        if (num==0){
            return new int[1];
        }
        int[] arr = new int[num + 1];
        arr[0]= 0;
        arr[1]= 1;
        for (int i=1;i<arr.length;i++){
            int f=1;
            while (i>>f!=0){
                f++;
            }
            f= f -1;
            //移位运算的优先级小于加减运算的优先级，运算时先进行加减
            int n=1<<f;
            if (i==n){
                arr[i] = 1;
            }else {
                arr[i] = arr[n] + arr[i-n];
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        int num = 1;
        int f = 1;
        while (num>>f!=0){
            f++;
        }
        System.out.println(f);
        System.out.println(1<<f-1);
    }

    
    /**
     * 官方题解
     * 最直观的方法是对从 000 到 num\textit{num}num 的每个数直接计算「一比特数」。
     *
     * 每个 int\texttt{int}int 型的数都可以用 323232 位二进制数表示，只要遍历其二进制表示的每一位即可得到 111 的数目。
     *
     * 利用位运算的技巧，可以在一定程度上提升计算速度。按位与运算（&）的一个性质是：对于任意整数 x，令 x=x&(x−1) 该运算将 x 的二进制表示的最后一个 1 变成 0。
     * 因此，对 x 重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
     *
     * 另外，部分编程语言有相应的内置函数，例如 Java\texttt{Java}Java 的 Integer.bitCount\texttt{Integer.bitCount}Integer.bitCount，C++\texttt{C++}C++ 的 __builtin_popcount\texttt{\_\_builtin\_popcount}__builtin_popcount，Go\texttt{Go}Go 的 bits.OnesCount\texttt{bits.OnesCount}bits.OnesCount 等，读者可以自行尝试。需要注意的是，使用编程语言的内置函数时，不适用本方法的时间复杂度分析。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int[] 遍历(int num) {
        int[] bits = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            bits[i] = countOnes(i);
        }
        return bits;
    }

    public int countOnes(int x) {
        int ones = 0;
        while (x > 0) {
            x &= (x - 1);
            ones++;
        }
        return ones;
    }

    /**
     * 官方题解 动态规划
     * 对于正整数 xxx，如果可以知道最大的正整数 yyy，使得 y≤xy \le xy≤x 且 yyy 是 222 的整数次幂，则 yyy 的二进制表示中只有最高位是 111，其余都是 000，此时称 yyy 为 xxx 的「最高有效位」。令 z=x−yz=x-yz=x−y，显然 0≤z<x0 \le z<x0≤z<x，则 bits[x]=bits[z]+1\textit{bits}[x]=\textit{bits}[z]+1bits[x]=bits[z]+1。
     *
     * 为了判断一个正整数是不是 222 的整数次幂，可以利用方法一中提到的按位与运算的性质。如果正整数 yyy 是 222 的整数次幂，则 yyy 的二进制表示中只有最高位是 111，其余都是 000，因此 y&(y−1)=0y \&(y-1)=0y&(y−1)=0。由此可见，正整数 yyy 是 222 的整数次幂，当且仅当 y&(y−1)=0y \&(y-1)=0y&(y−1)=0。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */

    //&运算规则：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0
    public int[] 官方题解(int num) {
        int[] bits = new int[num + 1];
        //最大2的幂
        int highBit = 0;
        for (int i = 1; i <= num; i++) {
            if ((i & (i - 1)) == 0) {
                highBit = i;
            }
            //bit[2的幂] = 0+1;
            //bit[i] = bit[i-2的幂] + 1;
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }


}
